package com.lsa.letcode.the120.triangle;

import java.util.Arrays;
import java.util.List;

/**
 */
public class Solution {
    public int minimumTotal(List<List<Integer>> t) {
    	if (t.size() < 1) {
    		return 0;
    	}
    	
//    	best sum to get to current row
//    	i-th element is the best way (min path sum including col i) to get to ith column
		int[] totals = new int[t.size()];

//    	best sum to get to current row
//		we iterate on current row and relax totals for the next row
    	int[] nextTotals = new int[t.size()];
    	Arrays.fill(nextTotals, Integer.MAX_VALUE);
    	
    	totals[0] = t.get(0).get(0);
    	
        for (int r = 0; r < t.size() - 1; r++) {
        	List<Integer> row = t.get(r);
        	List<Integer> nextRow = t.get(r + 1);
			for (int c = 0; c < row.size(); c++) {
				int newValue = totals[c] + nextRow.get(c);
				if (newValue < nextTotals[c]) { // try relax
					nextTotals[c] = newValue; // relax
				}
				newValue = totals[c] + nextRow.get(c + 1);
				if (newValue < nextTotals[c + 1]) { // try relax
					nextTotals[c + 1] = newValue; // relax
				}
			}
			
			//swap totals ands nextTotals 
			int[] temp = totals;
			totals = nextTotals;
			nextTotals = temp;
        	
			// set nextTotals to Integer.MAX_VALUE to set initial condition for the relax procedure.
			Arrays.fill(nextTotals, Integer.MAX_VALUE);
		}
        int bestSum = Integer.MAX_VALUE;
        for (int i = 0; i < totals.length; i++) {
        	if (totals[i] < bestSum){
        		bestSum = totals[i];
        	}
		}
//        System.out.println(Arrays.toString(totals));
        return bestSum;
    }
}